The transmission of television signals in our society is widespread. The type of television transmission most familiar to the public is conventional broadcast television which occurs on VHF and UHF television channels. These television channels each have an assigned bandwidth of 6 megahertz (MHz). In some areas of the country, it would be desirable to have additional channel capacity available, as by the use of narrower channel bandwidth. While it is technologically feasible to significantly reduce the bandwidth required for conventional television broadcasting by modern coding methods, the enormous cost of changing millions of television receivers to accommodate this coding is prohibitive.
In addition to terrestrial broadcast, there are many other uses of broadcast or point-to-point transmitted television in our society. For example, international satellite television links transmit live programs around the world, television networks distribute network programming to their affiliates, and weather and earth-resource satellites transmit television signals representing their pictures. Furthermore, video teleconferencing and facsimile transmission of newspapers and printed material is receiving increasing attention. In many of these applications, it is highly desirable to reduce the required transmission bandwidth or data rate to the minimum possible, in order that a satellite or other transmission link may carry the maximum number of individual television pictures. A large body of art has arisen which is directed toward schemes for coding television signals to take advantage of the redundancy of the television signals in various manners for data rate reduction, as described for example in the article "Picture Coding: A Review" by Netravali et al., published at pages 366-406 of the proceedings of the IEEE, Volume 68, No. 3, March 1980.
According to Netravali, in addition to pulse code modulation (PCM), coding is classified in the major categories of (a) transform coding, (b) interpolate/extrapolate coding, (c) predictive coding and (d) miscellaneous coding. Pulse oode modulation merely transforms the television signal into a digital signal, which in general is not a bandwidth efficient code. Transform coding breaks the television signal into blocks of data which may be considered to be subpictures, and represents the subpictures as linear combinations of certain standard subpictures. The proportion of each standard picture is termed a coefficient. The interpolate/extrapolate coder attempts the send certain samples to the receiver and to either interpolate or extrapolate the remainder of the samples. The miscellaneous schemes include conditional replenishment, in which individual line element sample signals from a successive field of information are compared with the corresponding line elements in the previous field, and the difference therebetween is tested against a fixed threshold. If the difference exceeds the threshold value the new value is encoded and transmitted to a receiving station, along with an appropriate address code, as described in U.S. Pat. No. 4,541,012 issued Sept. 10, 1985, to Tescher. In general, conditional replenishment techniques are not optimum because the addresses of the transmitted samples must be transmitted.
The predictive coding technique is effective for reducing the data rate. In predictive coding, the transmitter generates an error signal for transmission to the receiver which represents the difference between a current data word representing a picture element (pixel or pel) which the transmitter is receiving and a reference or "predicted" data word representing a pixel which is generated by the receiver. It should be noted that the word "pixel" is often used to denote the data word representing a pixel or the value of the data word by which a pixel is represented. The transmitter knows the value of the predicted data word or pixel in a predictive coding system, because the transmitter includes a prediction circuit which is identical to the prediction circuit in the receiver which is producing the predicted pixel. The predicted reference pixel is often a corresponding pixel from a previous frame, or a weighted linear combination of pixels lying near the corresponding pixel of either the current or the previous frame. In this context, "near" means close physical proximity in the two-dimensional picture or raster of which the pixels are a part.
FIG. 1 illustrates in block diagram form a communication system using predictive coding techniques. In FIG. 1, a transmitter 10 communicates by way of a narrow bandwidth data channel 30 with a receiver 38. Transmitter 10 includes a source 12 of frame-sequential, line-scanned analog television signals which applies the analog television signals to an analog-to-digital converter (ADC) 14. ADC 14 samples the analog signals, quantizes them (represents the infinite range of values by a finite set of values) and digitizes them (represents each value of the set by a different digital number) to form digital signals which are made available on a conductor 15. Those skilled in the art understand that digital signals may be in either serial or parallel form, and that serial digital signals may be carried on a single conductor (together with its associated ground), while parallel signals must be carried by a set (a plurality) of conductors. Since this is well known, no distinction is made hereinafter between single conductors and sets of conductors. The digital signals produced by ADC 14 on conductor 15 are applied to the noninverting (+) input terminal of a subtracting circuit or subtractor 16 which receives a delayed predicted signal from conductor 25 at its inverting (-) input terminal. The predicted signal applied to the inverting input terminal of subtractor 16 is subtracted from the current value of the signal then being applied to the noninverting input terminal of adder 16 from conductor 15. A difference signal is generated at the output of subtractor 16. The difference signal is often known as an error signal. Since ADC 14 quantized the signal, the error signal at the output of subtractor 16 is also quantized. While not absolutely necessary to an understanding of predictive coding systems and not essential to operation of predictive coding systems generally or to operation of predictive coding systems according to the invention, a coarse quantizer illustrated as a block 18 is often coupled to the output of subtractor 16 to coarsely quantize the difference signal into a number of "bins". The bin is itself represented by a digital number, so the output of quantizer 18 on conductor 19 is a quantized difference signal, just as is the signal on conductor 17. The term difference (or error) signal hereinafter refers to the difference (error) signal on either conductors 17 or 19, without regard to the magnitude of the quantizing steps.
The difference or error signal on conductor 19 is applied to a predictor loop designated generally as 20. Predictor loop 20 is a replica of the circuit 40 in receiver 38 which regenerates each pixel to be displayed in succession from the signal transmitted over channel 30. Predictor loop 20 includes a summer or adder 22 which receives the difference or error signal from conductor 19. Adder 22 adds to the difference or error signal the delayed value of the predicted signal to produce a new predicted signal which is made available on a conductor 23 to a predictor and delay circuit 24. Predictor and delay circuit 24 delays the new predicted signal for a predetermined length of time, and may perform other processing steps, as mentioned, such as averaging together nearby pixels. For example, the delay associated with predictor and delay circuit 24 can be one frame interval. A delay magnitude of one frame interval indicates that the intensity value of a pixel of a frame is generally expected to be the same as the value of the corresponding pixel of the preceding frame. For a still picture, this will be true for every pixel Even in a picture having some motion, it will be true for many pixels. The new value of the predicted signal appearing on conductor 23 is a current predicted signal, which is delayed by the frame interval in predictor delay circuit 24 to become a delayed predicted signal on conductor 25. The delayed predicted signal on conductor 25 is applied to the inverting input terminal of subtractor 16 and to the input terminal of adder 22, as mentioned. As described, each pixel is characterized by a single value, which may be considered to be the luminance of a monochrome (black-and-white) picture. Those skilled in the art will realize that it may also represent the intensity of any one of a plurality of components of a color signal.
The difference or error signal on conductor 19 is also applied to a coding circuit illustrated as a coder 26. Coder 26 encodes the difference signal in known fashion, as by run length coding and/or Huffman coding. Run length coding and Huffman coding have the effect of drastically reducing the data rate, and also cause the data rate to be variable. In order to eliminate the variability of the data rate, a rate buffer 28 is coupled to coder 26 for receiving or being laden with coded difference data at a variable rate, for temporarily storing the coded difference data, and for applying the coded difference data at a constant rate through channel 30 to receiver 38. This type of buffer is often known as a first-in, first-out (FIFO) memory.
Receiver 38 receives coded difference data at a constant rate from channel 30, and stores the coded difference data in a rate buffer 48. Data is supplied therefrom as required to a decoder 46, which accepts the run length and Huffman-coded difference data at a variable rate, and decodes it into difference or error signals available on conductor 59, exactly corresponding to the signals which were available on conductor 19 of transmitter 10 (except for transmission errors, which are not considered herein). The decoded difference or error signals are applied to an input terminal of a summer or adder 42 of a predictor loop designated generally as 40. Adder 42 adds together the difference or error signal appearing on conductor 59 and the delayed predicted signal appearing on conductor 45, to produce a new predicted signal on a conductor 43, which is applied to a digital-to-analog converter (DAC) 54 for generating an analog signal, which is applied to a television display circuit illustrated as a block 52 for display of the picture. The new predicted signal is also applied from conductor 43 to a predictor and delay circuit 44 which is identical to predictor and delay circuit 24 of transmitter 10. Since predictor and delay circuit 44 is identical to predictor and delay circuit 24, the new predicted signal on conductor 43 appears on conductor 45 after a corresponding delay, which in the example is one frame interval. The resulting delayed predicted signal on conductor 45 is applied to adder 42, as mentioned.
The signal on conductor 19 of transmitter 10 and the signal on conductor 59 of receiver 38 are identical (except for a time lag due to the time required for transmission therebetween), because decoder 46 performs a transformation which is the precise inverse of that performed by coder 26. Difference signals applied by conductor 19 to adder 22 are therefore identical to the signals applied from conductor 59 to adder 42, and since predictor 20 is identical to predictor 40, the new predicted signals produced on conductors 23 and 43 are identical, except for the transmission time lag (which has no significant effect, and is hereinafter ignored). Since predictor and delay circuits 24 and 44 are identical, and each receives the new predicted signal at its input, each produces identical delayed predicted signals on its output conductor (25 and 45). Thus, transmitter 10 produces on conductor 23 a signal identical to that which receiver 38 currently produces for display. For this purpose, the term "currently" does not refer to concurrence in time, but rather to concurrence of television frame number and raster position. Consequently, transmitter 10 always has available to it at the inverting input of subtractor 16 a delayed predicted signal identical to that generated by receiver 38 for the corresponding pixel of the previous frame. Therefore, the error signal being transmitted at any moment from transmitter 10 is the difference between the television signal then being applied on conductor 15 to subtractor 16, from which is subtracted a signal corresponding to that produced and displayed by receiver 38 for the previous frame. It should be noted that during system design experimentation relating to predictor and quantizer effects, a receiver 38 may not be used; the signal on conductor 23 of the transmitter is considered to be a replica of the signal produced on conductor 43 by such a receiver.
Predictive systems such as that illustrated in FIG. 1 can achieve very large reductions in data rate, especially on still pictures. However, when the picture has motion, the predicted signal may at times be most unlike the actual current value. When there is substantial motion in the television picture, the difference or error signals on conductor 19 tend to be large in value and to change rapidly. Consequently, run length coding tends to be relatively less effective in reducing data rate, and Huffman coding tends to produce relatively longer code words. Since the data rate of channel 30 is preestablished and rate buffer 28 of transmitter 10 can only transmit data at the maximum rate allowed by channel 30, it is possible for rate buffer 28 to become overfull or to "overflow" when the average size of the code word length is large, and code words are applied to the rate buffer for a long period of time at a high rate. The term "overfull" and "overflow," may not be sufficiently descriptive. The rate buffer is "laden" or loaded by the difference between the variable flow of code words into the buffer and the fixed flow of code words out of the buffer, which forms a "lading" or loading which varies with time. The capacity of the buffer is the maximum lading which it can hold. The lading may from moment to moment vary from zero (empty buffer) to the maximum capacity of the buffer (corresponding to a full buffer). Any attempt to increase the lading, even by one bit, creates an "overflow" condition. "Underflow" occurs when the buffer writes or attempts to write to the outside world a number of bits which exceeds the number of bits in the lading, with the result that meaningless zero values are transmitted as meaningful data. When the lading is such that underflow or overflow occurs, some code words may not be stored in rate buffer 28, or are corrupted, and are therefore lost. The loss or corruption of code words is very serious in a predictive encoding type of communication system, and leads to substantial errors in data transmission and consequent distortions of the transmitted picture.
It should be noted that the quantizer (18) in these loops is recognized as being a nonlinear element, which makes rigorous analysis difficult. Furthermore, the quantizer may have quantizing steps of different sizes, which increases the nonlinearity. However, ignoring the nonlinearity in the analysis produces results which, while not rigorous, indicate trends, and which can therefore be useful.
A known method for stabilizing the lading of the rate buffer (and therefore preventing exceeding the capacity of the buffer by underflow or overflow) is to sense the amount of lading of the rate buffer, and to generate a control signal which is applied to at least one of the elements of the predictive coding system which produces the coded difference signal to reduce the rate of generation of the code words when the control signal indicates that the buffer is above or below a certain lading level.
FIG. 2 illustrates a predictive encoding system similar to FIG. 1 The arrangement of FIG. 2 differs from the arrangement of FIG. 1 in that a fill control circuit illustrated as a block 210 is coupled to rate buffer 28 in transmitter 110 for producing a control signal on a conductor 212 representing the occupancy (level of fill or lading level) of rate buffer 58. The control signal on conductor 212 is applied to a decimator illustrated as a block 214, which is connected by conductors 15 and 15' between ADC 14 and the noninverting input terminal of subtractor 16. Decimator 214 is intended to reduce the data rate by decimating pixels, lines or frames. In this context, decimation means deletion of a proportion of the total number of pixels, lines or frames. For purposes of explanation, the description hereinafter assumes that pixels are being decimated. As a more specific example, decimator 214 could eliminate the data word corresponding to every other pixel, which would therefore reduce the true data rate by a factor of 2. This is a drastic reduction in data rate, and other reductions might be preferable, as for example elimination of one out of three (3:2) or one out of four (4:3) pixels. Decimators may be implemented as switches which alternately pass and block the pixels applied thereto, or they may include a sample-and-hold function operated at a clock rate lower than the clock rate of the applied signals, or the like. However implemented, decimator 214 when it is in the decimation mode reduces the true data rate being applied over conductor 15 to the noninverting input terminal of subtractor 16.
Since the purpose of the decimating scheme is to reduce the number of difference words applied to buffer 28 by reducing the number of words applied to coder 26, coder 26 must have at least its input clock rate adjusted in response to the selected operating mode of decimator 214, if appropriate. Since the output clocking of coder 26 is asynchronous, this clocking need not be changed in response to the operating mode of the decimator.
Decimator 214 has an effect generally similar to that of a filter. When in a decimation mode, decimator 214 tends to reduce the amount of high frequency data coupled through the system. To the extent that introduction of the decimator does not change the operation or timing of those elements of transmitter 110 which are downstream from the decimator, it also has no effect on receiver 238 other than affecting the high frequency content of the reproduced picture. Since alternate pixels are being deleted in the aforementioned specific example, receiver 238 must accommodate the reduced data rate as by sample-and-holding each pixel for an additional clock period, or by interpolating each missing pixel from its neighbors in an expander. The expander is illustrated as a block 264. There are, however, some problems with the arrangement of FIG. 2.
Some of the problems associated with the arrangement of FIG. 2 are explained with reference to FIG. 3, which is a skeletonized or simplified version of FIG. 2. Elements of FIG. 3 corresponding to those of FIG. 2 are designated by the same reference numerals. Decimator 214 may take any of several forms. Some of the problems are less severe with 2:1 decimation, but as mentioned other decimation ratios may be more advantageous. A simple 2:1 decimator could be implemented by a simple switch, which passes alternate pixels and, for those pixels which are not passed, provides a reference value such as zero on conductor 15'. The first problem which arises when the decimator is switched from a nondecimating mode into the decimating mode is that every other pixel arriving at adder 16 from conductor 15' has zero value, whereas for at least one frame interval following the switchover, each pixel arriving at adder 16 from conductor 25 has a finite value. Consequently, for each correct difference signal generated on conductor 17, at the next clock cycle there follows a difference signal which is the inverse of the corresponding pixel from the previous frame. This inverse pixel occurs because subtractor 16 subtracts the predicted signal (the subtrahend) on conductor 25 (where every pixel has a finite value) from the zero value of the decimated pixel arriving from conductor 15' (the minuend), by inverting the polarity of the predicted signal on conductor 25 and adding it to the zero value on conductor 16, thereby producing a full value (not a difference) corresponding to the magnitude of the pixel of the previous frame, but of opposite polarity. It is clear that these full-value, inverted signals should not be transmitted through channel 30 to receiver 338, because they will result in large codewords, which is contrary to the desired end of reducing the data rate. On the other hand, these full-value, inverted pixels are circulating in predictor loop 20, and if they are somehow prevented from reaching receiver 338, predictor loop 40 will circulate values which do not correspond with those circulating in loop 20. As a result, the reproduced picture will undesirably diverge from the picture being transmitted.
As mentioned above, 2:1 decimation is extreme, and lesser values will generally be desired. Decimators for values other than 2:1 are known in the prior art. Such a decimator (termed a sample rate converter) is described, for example, in U.S. Pat. No. 4,568,965 issued Feb. 4, 1986, in the name of Powers. Such decimators or sample rate converters do not simply delete occasional pixels, but rather produce new sets of pixels with a new clock timing, so that signal is always available on each clock cycle. Thus, rather than calling such a sample rate converter a decimator, it might better be termed a data density "reducer" which reduces the sample density. For simplicity, assume that reducer 214 of FIG. 3 is a 4:3 reducer, which, for each four pixels received over conductor 15, produces on conductor 15' three new pixels, the values of which are related to the values of the four incoming pixels. Therefore, the input section of reducer 214 has a higher data density or data rate than does the output section of the reducer. In this example the data density or data rate at the reducer input is 4/3 higher than at its output. At the moment at which decimator or reducer 214 is switched from a nonreducing to a reducing mode (or from one reducing mode to a further reducing mode), the clocking of the signals arriving at adder 16 from conductors 15' and 25 becomes disparate. That is to say, that predictor loop 20 is clocked at a higher rate than reducer 214, and is producing more samples during each unit time for application over conductor 25 to the inverting input of subtractor 16 than reducer 214 is producing for application to the noninverting input of subtractor 16. More specifically, in the case of 4:3 reduction, each clock cycle of the signal arriving at adder 16 from conductor 15' has a duration of 1 1/3 times the duration of each clock cycle arriving from conductor 25. It is not clear how this can be handled in subtractor 16. The mathematics of summation would certainly be complex.
FIG. 4 illustrates a possible scheme which might be considered for eliminating the problem of different data densities at subtractor 16 in the arrangement of FIG. 3. The arrangement of FIG. 4 is similar to the arrangement of FIG. 3, and elements of FIG. 4 corresponding to those of FIG. 3 are designated by the same reference numerals. FIG. 4 differs from FIG. 3 in that a second decimator or data density reducer designated 314, and identical to reducer 214, is coupled between the output of predictor and delay circuit 24 and the inverting input of subtractor 16. Reducer 314, being identical to reducer 214, causes the data rate or data density on conductor 25' to equal that on conductor 15', so that subtractor 16 can operate in a simple and straightforward fashion to produce difference signals on conductors 17 and 19 at the lower data density. However, this simply transfers the data density problem to adder 22. This can be readily understood by noting that the error signals applied to adder 22 from conductor 19 are at a relatively lower data density, but the predicted signal produced by predictor and delay circuit 24 and applied by conductor 25 to the other input of adder 22 is at the higher data density. Furthermore, it is not clear what must be done at the receiver to compensate for the effect of reducer 314, taking into account that the predictor loops in the transmitter and receiver must be identical.
FIG. 5 is similar to FIG. 4, but with data density reducer 314 replaced by a reducer 514 connected in a slightly different position, and with a further matching reducer 564 added to receiver 538. Otherwise, FIG. 5 is identical to FIG. 4. Reducer 514 is coupled between the output of predictor and delay circuit 24 and conductor 25, and is placed in operation simultaneously with reducer 214. With the illustrated location of reducer 514, when reducers 214 and 514 are operating in a data or pixel reducing mode, the reduced data density appears on conductor 25, so that subtractor 16 operates with reduced data density at both inputs, and adder 22 likewise operates with equal data densities at both inputs. Similarly, adder 42 of receiver 538 operates with reduced data at both its inputs. However, new problems have arisen. In FIG. 5, one problem is represented by the numerals 3 and 4 associated with the input and output ends of reducer 514 and of predictor and delay circuit 24. The numerals 3 represent the lower clock rate associated with the output signal of reducer 514 and the input signal of predictor and delay circuit 24, while the numerals 4 represent the higher clock rate associated with the output signal from predictor and delay circuit 24 and the input of reducer 514. In some way, predictor and delay circuit 24 must accept three data samples per unit time, and produce or output four data samples in that unit time. This is not a simple matter, especially when considering that more than one mode of operation is required. The first mode of operation corresponds to the mode when no data reduction is necessary, and a second mode is the reducing mode. Furthermore, it may be desirable to have further values of data reduction other than 4:3, as for example 8:7, and there must therefore be provision for many operating modes. The same problem also arises at the receiver. Remember that receiver prediction loop 40 must be identical to transmitter prediction loop 20. Since loop 20 includes a reducer 514 connected to the output terminal of predictor and delay circuit 24, loop 40 also includes a reducer illustrated as 564 connected to the output of prediction and delay circuit 44. Some way must also be found to cope with the fact that before decimation begins, predictor and delay circuit 24 of transmitter 510 contains a full frame of full density data, but during reduced data operation it contains less information; it would appear that to prevent artifacts, an entire frame of stored data must be reduced instantly at the moment of switchover. Correspondingly, when switching out of the data reduction mode, the data then stored in predictor and delay circuit 24 must instantaneously be augmented. This problem also occurs at the receiver, in that at the moment of changing modes, the data stored in predictor and delay circuit 44 must be instantaneously increased or decreased.
U.S. Pat. No. 4,488,175 issued Dec. 11, 1984, to Netravali describes a predictive coding communication system in which a 2:1 decimator (213) follows the predictive loop in the transmitter and acts on the difference signal flowing to the coder. In this arrangement, the difference signal produced at the output of the subtracting circuit (207) in the transmitter has full data density at all times. However, the corresponding predictor in the receiver receives as an input signal difference signals having 2:1 density reduction. Thus, the predictor loops in the transmitter and the receiver are fundamentally different. In order to cause the predictor loop in Netravali's transmitter to produce substantially correct predicted signals (signals corresponding to those produced by the receiver), the path to the input to the predictor and delay circuit of the transmitter (201) from the transmitter adder (209) includes a switched circuit (including elements 210, 211, 212 and 250) which produces samples which during alternate clock cycles are simply the output pixel of the adder, and which during the next clock cycle are the average of two adjacent pixels. The Netravali arrangement has no data density problems associated with the predictor loop, because its reducer or decimator is coupled between the predictor loop and the coder. The Netravali system has the problem of lack of identity of the transmitter and receiver prediction loops, and does not seem to be amenable to data reductions other than 2:1, because simple dropping of pixels, other than in a 2:1 pattern, produces an undesirable pattern in the reproduced picture.